In user authentication systems, a one-time password-based system using a single-use password usable only once for user authentication purpose has become popular as one scheme having higher security than fixed password-based schemes. The one-time password-based system includes a token-based scheme using a token for creating a one-time password in accordance with a one-time-password generation rule synchronous with an authentication server, and a challenge/response scheme designed such that an authentication server transmits to a client a so-called “challenge” which is a value to be varied every time, and the client returns to the authentication server a response created by applying a client's fixed password to the challenge in accordance with a given rule. While the token-based scheme has an advantage of being able to reliably identify a user who owns a token, it forces the user to carry around the token, and has problems about cost of the token and security in the event of loss of the token. In this respect, the challenge/response scheme offers the convenience of being not necessary to use a token. On the other hand, due to a process of generating a one-time password using a client's fixed password which is highly likely to be analogized, the challenge/response scheme involves problems about poor protection against stealing during a password input operation and the need for installing dedicated software to allow a client to generate a response.
Late years, a new user authentication system has been developed based on a so-called “matrix authentication” scheme to improve the above problems in the conventional challenge/response scheme, (see, for example, the following Patent Publication 1 and Non-Patent Publication 1). This matrix authentication scheme is designed to arrange a plurality of random numbers in a given pattern format so as to create a matrix-form presentation pattern to be presented to a user subject to authentication, and apply a one-time-password derivation rule serving as a password of the user to certain pattern elements (a part of the random numbers) included in the presentation pattern so as to create a one-time password. Specifically, the presentation pattern is shared in common between a server and a client. Then, instead of a direct comparison of password, the sever carries out user authentication by comparing between a one-time password created on the client side as a result of applying the one-time-password derivation rule or the user's password to the presentation pattern, and a verification code created on the server side as a result of applying the one-time-password derivation rule or the user's password to the presentation pattern. In the matrix authentication scheme, a one-time-password derivation rule serving as a password is information about respective positions of certain pattern elements to be selected on a matrix-form presentation pattern and a selection order of the certain pattern elements, and characterized in that it is easily storable in the form of an image and cannot be figured out as a specific password even if being stolen during a password input operation.
FIG. 9 is a block diagram showing a user authentication system 100 based on a typical conventional matrix authentication scheme. In this conventional matrix authentication scheme, information for creating a presentation pattern 191 is transmitted from an authentication server 101 to an authentication-requesting client 151 in the form of a pattern element sequence 190 (see, for example, the Patent Publication 1). Specifically, the user authentication system 100 generally comprises the authentication server 101 for carrying out user authentication, and the authentication-requesting client 151 serving as a terminal for allowing each user to request authentication. The authentication server 101 includes a one-time-password-derivation-rule storage section 102, user-ID receiving means 103, pattern generation means 104, pattern transmission means 105, verification-code creation means 106, one-time-password receiving means 107 and user authentication means 108. The authentication-requesting client 151 includes user-ID input means 152, user-ID transmission means 153, pattern receiving means 154, pattern display means 155, one-time-password input means 156 and one-time-password transmission means 157.
The authentication-requesting client 151 includes user-ID input means 152, user-ID transmission means 153, pattern receiving means 154, pattern display means 155, one-time-password input means 156 and one-time-password transmission means 157.
In the authentication server 101, the one-time-password-derivation-rule storage section 102 pre-stores respective user IDs 102a and one-time password rules 102b of users in associated relation with each other on a user-by-user basis. The user-ID receiving means 103 is operable to receive the user ID 181 of the user subject to authentication, from the authentication-requesting client 151. The pattern generation means 104 is operable, in accordance with a given generation rule, such as a pseudorandom-number generation rule, to generate a pattern element sequence 190 which is a sequence of pattern elements to be included in a matrix-form presentation pattern 191. The pattern transmission means 105 is operable to transmit the generated pattern element sequence 190 to the authentication-requesting client 151.
In the authentication-requesting client 151, the user-ID input means 152, such as a keyboard, allows the user subject to authentication to enter his/her own user ID 181 therefrom. The user-ID transmission means 153 is operable to transmit the entered user ID 181 to the authentication server 101. Thus, in the authentication server 101, the user-ID receiving means 103 receives the transmitted user ID 181. Then, in accordance with the given generation rule, the pattern generation means 104 generates a pattern element sequence 190 or a sequence of random numbers for forming a matrix-form presentation pattern 191. The pattern transmission means 105 transmits the generated pattern element sequence 190 to the authentication-requesting client 151. In the authentication-requesting client 151, the pattern receiving means 154 is operable to receive the transmitted pattern element sequence 190. The pattern display means 155 is operable to arrange the respective pattern elements included in the received pattern element sequence 190, in a given pattern format 191p, so as to create a presentation pattern 191, and display the presentation pattern 191 on a screen.
FIG. 10 is an explanatory conceptual diagram showing a process of creating a presentation pattern 191 in the conventional user authentication system 100. FIG. 10 shows a presentation pattern 191 as one example in which one-digit numerals of “0 (zero)” to “9” are used as pattern elements, and sixty four of the pattern elements are arranged, respectively, at element positions in a pattern format consisting of four 4×4 matrixes. In this example, the authentication server 101 is operable to generate, in accordance with a random-number generation algorithm, sixty four of the one-digit numerals which are pattern elements to be included in the presentation pattern 191, and then transmit a pattern element sequence 190 created by sequencing the generated pattern elements, to the authentication-requesting client 151. The authentication-requesting client 151 is operable to receive the pattern element sequence 190, and arrange the pattern elements included therein, respectively, at element positions on the given pattern format 191p (consisting of four 4×4 matrixes, in this example) in order in conformity to the order in pattern element sequence 190, so as to create the presentation pattern 191, and display the created presentation pattern 191 on the screen.
FIG. 7 is an explanatory conceptual diagram showing a process of entering a one-time password in the matrix authentication scheme. The user selects certain ones of the numerals displayed at given positions on the matrixes in order by applying the one-time-password derivation rule 102b of the user to the presentation pattern 191, and enters the selected numerals as a one-time password from the one-time-password input means 156. Further, a certain number of numerals may be additionally entered without being based on the presentation pattern 191. Specifically, a fixed password of the user may be included in the one-time password. These numerals are entered using a pointing device, such as a mouse or a touch panel, or a keyboard 196. The arrows and circles indicated by broken lines in FIG. 7 show that the one-time password based on the presentation pattern 191 is entered from the key board 196. Then, the one-time-password transmission means 157 is operable to transmit the entered one-time password 192 to the authentication server 101. In the authentication server 101, the one-time-password receiving means 107 is operable to receive the transmitted one-time password 192. The verification-code creation means 106 is operable to create a verification code as a result of applying the one-time-password derivation rule 102b associated with the received user ID 181, to certain pattern elements of a presentation pattern formed from the transmitted pattern sequence 190 on the server side. The user authentication means 108 is operable to compare the received one-time password 192 with the created verification code, and successfully authenticate the user if they are identical to one another.                [Parent Publication 1] Pamphlet of International Publication WO 03/069490 (lines 2 to 3, page 10)        [Non-Parent Publication 1] Taizu Ohnishi & Associates IT Conference,“Learn from Base Technologies -Mobile Management-”, IT SELECT, Mediaselect Inc., Feb. 01, 2002, pp 56 to 60        
In the conventional matrix authentication scheme, a pattern element sequence, or a sequence of pattern elements for forming a matrix-form presentation pattern, is transmitted from the authentication server to the authentication-requesting client. In this process, if information about the pattern element sequence is acquired by a malicious third party, through means, for example, of network tapping, the tapped information will bring about the possibility of estimating the presentation pattern based thereon. Only one tapping of a one-time password as a response to this presentation pattern is not enough to figure out the association between the selected pattern elements of the one-time password and the pattern elements of the presentation pattern in a one-to-one correspondence with each other, and therefore a one-time-password derivation rule or a password is never figured out as a specific one. However, if a pattern element sequence and a one-time password corresponding thereto are tapped plural times, respective positions of certain pattern elements to be selected as a one-time password from a presentation pattern can be narrowed down along with increase in tapped information, and finally the one-time-password derivation rule will be undesirably specified. Thus, there is a strong need for a matrix authentication scheme capable of reducing the risk of password leakage arising from the above network tapping by third parties.